堆排序

//
//  CSort.cpp
//  Lesson5
//
//  Created by ShenJun on 2017/1/19.
//  Copyright © 2017年 ShenJun. All rights reserved.
//

#include "CSort.hpp"



NS_BEGIN

void Swap(int& a, int&b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

// 交换数组中的两个元素
void Swap(int *arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 堆的调整
void HeapAdjust(int* arr, int node, int len)
{
    // node 是需要调整的节点 遍历节点的孩子 然后比较 和大的孩子交换位置
    for (int i = 2 * node; i < len; i *= 2)  // 说明有左孩子 但不一定有右孩子
    {
        int nodeIndex = i/2;
        int nodeValue = arr[nodeIndex];
        int maxChildIndex = i;

        if(i+1 < len)
        {
            // 说明有右孩子
            if(arr[i] < arr[i+1])
            {
                maxChildIndex++; // 找到大的孩子（右孩子）
            }
        }

        if(nodeValue >= arr[maxChildIndex]) continue;  // 说明节点比孩子大 则当前节点不需要调整

        arr[nodeIndex] = arr[maxChildIndex];           // 说明孩子比节点大 则交换
        arr[maxChildIndex] = nodeValue;
    }
}

// 对堆的排序
void HeapSort(int* arr, int len)
{
    for (int i = len/2; i > 0; i--) {    // 从后往前调整 叶子节点就不需要调整了
        HeapAdjust(arr, i, len);
    }

    // 上面的步骤调整完以后 第一个节点就是最大的

    for (int i = len - 1; i > 0; i--) {  // 把最大的一个元素放到最后 然后再调整堆 范围就是 [1 , lenth - i]
        Swap(arr, 1, i);  // 把最大的放到最后 然后把剩余的再重新调整
        HeapAdjust(arr, 1, i - 1);
    }
}


void Main()
{
//    InsertOrder();
//    BubbleOrder();
//    ExchangeOrder();

//    int a[] {70, 30, 20, 10, 60, 50, 90, 80, 40};
    int array[] {-1, 5, 7, 4, 8, 9, 11, 3, 43, 21, 33};
    HeapSort(array, 11);

//    QuickSort(array, 0, 10);
//    ShellSort(array, 11);

    for (int i = 0; i < 11; i++) {
        std::cout << array[i] << std::endl;
    }
}

NS_END